//==========================================================================
// Copyright (c) 2000-2008,  Elastos, Inc.  All Rights Reserved.
//==========================================================================

#define __NO_LINKNODE_CONSTRUCTOR

#include <core.h>
#include <_hal.h>
#include <_schedule.h>

//
// TimeSharingScheduleClass
//
STATIC Int32 BalancerRoutine(void *pvParameter)
{
    assert(pvParameter);

    ((TimeSharingScheduleClass *)pvParameter)->PromoteHungryThreads();
    return 0;
}

void TimeSharingScheduleClass::Initialize()
{
    AddPeriodicTask(1, &BalancerRoutine, this);
}

void TimeSharingScheduleClass::InitializeThread(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pScheduleClass == this);

    pThread->m_uBasePriority = TIMESHARING_DEFAULT_PRIORITY;
    pThread->m_uDynamicPriority = TIMESHARING_DEFAULT_PRIORITY;
    pThread->m_nTimeQuota = s_nBaseTimeQuotas[TIMESHARING_DEFAULT_PRIORITY];

    pThread->m_bInherit = FALSE;

    pThread->m_pEffectiveScheduleClass = pThread->m_pScheduleClass;
    pThread->m_uEffectiveSchedulePolicy = pThread->m_uSchedulePolicy;

    pThread->m_uEffectiveBasePriority = pThread->m_uBasePriority;
    pThread->m_uEffectiveDynamicPriority = pThread->m_uDynamicPriority;
    pThread->m_nEffectiveTimeQuota = pThread->m_nTimeQuota;
}

void TimeSharingScheduleClass::SetThreadPriority(
    Thread *pThread, ThreadPriority priority, bool_t bRunning)
{
    assert(pThread);
    assert(pThread->m_pScheduleClass == this);
    assert(ThreadPriority_Highest >= priority);

    register uint_t uPriority = priority >> 5;
    assert(TIMESHARING_MAX_PRIORITY >= uPriority);

    if (uPriority == pThread->m_uBasePriority) return;

    pThread->m_uBasePriority = uPriority;

    if (pThread->m_nTimeQuota > s_nMaxTimeQuotas[uPriority]) {
        pThread->m_nTimeQuota = s_nMaxTimeQuotas[uPriority];
    }

    if (pThread->m_uDynamicPriority > s_uHighDynamicPriorities[uPriority]) {
        pThread->m_uDynamicPriority = s_uHighDynamicPriorities[uPriority];
    }
    else if (pThread->m_uDynamicPriority
        < s_uLowDynamicPriorities[uPriority]) {
        pThread->m_uDynamicPriority = s_uLowDynamicPriorities[uPriority];
    }

    if (pThread->m_bInherit) return;

    pThread->m_uEffectiveBasePriority = uPriority;
    pThread->m_nEffectiveTimeQuota = pThread->m_nTimeQuota;

    if (pThread->m_uEffectiveDynamicPriority != pThread->m_uDynamicPriority) {
        if (bRunning) {
            pThread->Detach();
            m_listHeads[pThread->m_uDynamicPriority].InsertLast(pThread);
            RecalcMaxActivePriority(pThread->m_uDynamicPriority);
        }

        pThread->m_uEffectiveDynamicPriority = pThread->m_uDynamicPriority;
    }
}

ThreadPriority TimeSharingScheduleClass::GetThreadPriority(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pScheduleClass == this);

    return (0 == pThread->m_uBasePriority)?
            0 : (pThread->m_uBasePriority << 5) + 0x1f;
}

void TimeSharingScheduleClass::OnThreadSleep(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pEffectiveScheduleClass == this);

    pThread->m_nEffectiveTimeQuota--;
    if (pThread->m_nEffectiveTimeQuota < 0) {
        pThread->m_nEffectiveTimeQuota = 0;
    }

    if (!pThread->m_bInherit) {
        pThread->m_nTimeQuota = pThread->m_nEffectiveTimeQuota;
    }
}

void TimeSharingScheduleClass::OnThreadWakeUp(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pEffectiveScheduleClass == this);

    if (pThread->m_uEffectiveDynamicPriority
        < s_uHighDynamicPriorities[pThread->m_uEffectiveBasePriority]) {
        pThread->m_uEffectiveDynamicPriority =
            s_uHighDynamicPriorities[pThread->m_uEffectiveBasePriority];
    }

    if (!pThread->m_bInherit) {
        pThread->m_uDynamicPriority = pThread->m_uEffectiveDynamicPriority;
    }
}

void TimeSharingScheduleClass::OnThreadYield(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pEffectiveScheduleClass == this);

    pThread->m_nEffectiveTimeQuota = 0;
    if (!pThread->m_bInherit) {
        pThread->m_nTimeQuota = 0;
    }

    pThread->Detach();

    UpdatePriorityByQuota(pThread);

    m_listHeads[pThread->m_uEffectiveDynamicPriority].InsertLast(pThread);

    RecalcMaxActivePriority(pThread->m_uEffectiveDynamicPriority);
}

void TimeSharingScheduleClass::OnThreadSwitchOut(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pEffectiveScheduleClass == this);

    pThread->m_uReadyStartTick = m_uElapsedTicks;
}

void TimeSharingScheduleClass::EnterRunningList(
    Thread *pThread, RunningReason reason)
{
    assert(pThread);

    pThread->m_uReadyStartTick = m_uElapsedTicks;
    m_listHeads[pThread->m_uEffectiveDynamicPriority].InsertLast(pThread);
    RecalcMaxActivePriority(pThread->m_uEffectiveDynamicPriority);
}

void TimeSharingScheduleClass::LeaveRunningList(Thread *pThread)
{
    assert(pThread);
    assert(pThread->m_pEffectiveScheduleClass == this);

    pThread->Detach();
    RecalcMaxActivePriority(-1);
}

void TimeSharingScheduleClass::UpdateTime(uint_t uTicks)
{
    m_uElapsedTicks += uTicks;
}

bool_t TimeSharingScheduleClass::UpdateThreadTime(
    Thread *pThread, uint_t uTicks)
{
    assert(pThread);
    assert(pThread->m_pEffectiveScheduleClass == this);

    pThread->m_nEffectiveTimeQuota -= uTicks * TIMESHARING_QUOTAS_PER_TICK;

    if (pThread->m_nEffectiveTimeQuota < 0) {
        pThread->m_nEffectiveTimeQuota = 0;
    }

    if (!pThread->m_bInherit) {
        pThread->m_nTimeQuota = pThread->m_nEffectiveTimeQuota;
    }

    if (0 == pThread->m_nEffectiveTimeQuota) {
        pThread->Detach();

        UpdatePriorityByQuota(pThread);

        m_listHeads[pThread->m_uEffectiveDynamicPriority].InsertLast(pThread);

        RecalcMaxActivePriority(pThread->m_uEffectiveDynamicPriority);

        return TRUE;
    }

    return FALSE;
}

Thread *TimeSharingScheduleClass::SelectNextThread()
{
    if (-1 == m_nMaxActivePriority) return NULL;

    assert(TIMESHARING_MIN_PRIORITY <= m_nMaxActivePriority
            && m_nMaxActivePriority <= TIMESHARING_MAX_PRIORITY);
    assert(!m_listHeads[m_nMaxActivePriority].IsEmpty());

    Thread *pThread = (Thread *)m_listHeads[m_nMaxActivePriority].First();

    return pThread;
}

TimeSharingScheduleClass::TimeSharingScheduleClass()
{
    m_type = ScheduleClassType_TimeSharing;

    m_uElapsedTicks = 0;

    for (uint_t i = 0; i < TIMESHARING_NUMBEROF_PRIORITIES; i++) {
        m_listHeads[i].Initialize();
    }

    m_nMaxActivePriority = -1;
}

void TimeSharingScheduleClass::RecalcMaxActivePriority(int nNewActivePriority)
{
    if (m_nMaxActivePriority < nNewActivePriority) {
        m_nMaxActivePriority = nNewActivePriority;
    }
    else if (m_nMaxActivePriority > nNewActivePriority) {
        for (int i = m_nMaxActivePriority; i > nNewActivePriority; i--) {
            if (!m_listHeads[i].IsEmpty()) {
                m_nMaxActivePriority = i;
                return;
            }
        }
        m_nMaxActivePriority = nNewActivePriority;
    }
}

INLINE bool_t TimeSharingScheduleClass::UpdatePriorityByQuota(Thread *pThread)
{
    assert(pThread);

    if (pThread->m_nEffectiveTimeQuota > 0) return FALSE;

    bool_t bPriorityDecrement = FALSE;

    if (pThread->m_uEffectiveDynamicPriority
        > pThread->m_uEffectiveBasePriority) {
        bPriorityDecrement = TRUE;

        if (pThread->m_uEffectiveDynamicPriority
            <= s_uHighDynamicPriorities[pThread->m_uEffectiveBasePriority]) {
            pThread->m_uEffectiveDynamicPriority--;
        }
        else {
            pThread->m_uEffectiveDynamicPriority =
                s_uHighDynamicPriorities[pThread->m_uEffectiveBasePriority];
        }
    }
    else {
        if (pThread->m_uEffectiveDynamicPriority
            > s_uLowDynamicPriorities[pThread->m_uEffectiveBasePriority]) {
            bPriorityDecrement = TRUE;

            pThread->m_uEffectiveDynamicPriority--;
        }
    }

    pThread->m_nEffectiveTimeQuota =
        s_nBaseTimeQuotas[pThread->m_uEffectiveBasePriority];

    if (!pThread->m_bInherit) {
        pThread->m_uDynamicPriority = pThread->m_uEffectiveDynamicPriority;
        pThread->m_nTimeQuota = pThread->m_nEffectiveTimeQuota;
    }

    return bPriorityDecrement;
}

INLINE void TimeSharingScheduleClass::TryToPromoteHungryThread(
    Thread *pThread)
{
    assert(pThread);

    uint_t uRatio =
        (uint_t)(m_uElapsedTicks - pThread->m_uReadyStartTick)
            / s_uReadyTickLimits[pThread->m_uEffectiveBasePriority];

    if (uRatio < 1) return;

    pThread->m_uReadyStartTick +=
        s_uReadyTickLimits[pThread->m_uEffectiveBasePriority] * uRatio;

    pThread->m_nEffectiveTimeQuota +=
        s_uTimeQuotaIncrements[pThread->m_uEffectiveBasePriority] * uRatio;
    if (pThread->m_nEffectiveTimeQuota
        > s_nMaxTimeQuotas[pThread->m_uEffectiveBasePriority]) {
        pThread->m_nEffectiveTimeQuota =
            s_nMaxTimeQuotas[pThread->m_uEffectiveBasePriority];
    }

    if (!pThread->m_bInherit) {
        pThread->m_nTimeQuota = pThread->m_nEffectiveTimeQuota;
    }

    register uint_t uNewDynamicPriority = pThread->m_uEffectiveDynamicPriority
        + s_uPriorityIncrements[pThread->m_uEffectiveBasePriority] * uRatio;
    if (uNewDynamicPriority
        > s_uMaxDynamicPriorities[pThread->m_uEffectiveBasePriority]) {
        uNewDynamicPriority =
            s_uMaxDynamicPriorities[pThread->m_uEffectiveBasePriority];
    }
    else if (uNewDynamicPriority
            < s_uLowDynamicPriorities[pThread->m_uEffectiveBasePriority]) {
        uNewDynamicPriority =
            s_uLowDynamicPriorities[pThread->m_uEffectiveBasePriority];
    }

    if (pThread->m_uEffectiveDynamicPriority == uNewDynamicPriority) return;

    pThread->Detach();

    pThread->m_uEffectiveDynamicPriority = uNewDynamicPriority;
    if (!pThread->m_bInherit) {
        pThread->m_uDynamicPriority = uNewDynamicPriority;
    }

    m_listHeads[pThread->m_uEffectiveDynamicPriority].InsertLast(pThread);

    RecalcMaxActivePriority(pThread->m_uEffectiveDynamicPriority);
}

void TimeSharingScheduleClass::PromoteHungryThreads()
{
//    kprintf("<$>");

    STATIC int s_nMaxActivePriority = TIMESHARING_MAX_PRIORITY;

    uint_t uNumberOfCheckedThreads = 0;
    for (int i = Min(s_nMaxActivePriority, m_nMaxActivePriority);
        i >= TIMESHARING_MIN_PRIORITY; i--) {
        uint32_t uFlags = SaveFlagsAndCli();

        Thread *pThread = (Thread *)m_listHeads[i].First();
        Thread *pNextThread;

        for (uint_t j = 0; (&m_listHeads[i] != pThread) && (j < 3); j++) {
            pNextThread = (Thread *)pThread->Next();

            TryToPromoteHungryThread(pThread);

            uNumberOfCheckedThreads++;
            if (16 <= uNumberOfCheckedThreads) {
                s_nMaxActivePriority = i;
                RestoreIF(uFlags);
                return;
            }

            pThread = pNextThread;
        }

        RestoreIF(uFlags);
    } // for

    s_nMaxActivePriority = TIMESHARING_MAX_PRIORITY;
}

// Schedule Tables
uint_t TimeSharingScheduleClass::s_uMaxDynamicPriorities[] = {
    31, 31, 31, 31,
    31, 31, 31, 31,
    31, 31, 31, 31,
    31, 31, 31, 31,
    31, 31, 31, 31,
    31, 31, 31, 31,
    31, 31, 31, 31,
    31, 31, 31, 31
};

uint_t TimeSharingScheduleClass::s_uHighDynamicPriorities[] = {
    7,  7,  7,  7,
    7,  7,  14, 14,
    14, 14, 14, 14,
    21, 21, 21, 21,
    21, 21, 21, 21,
    27, 27, 27, 27,
    27, 27, 31, 31,
    31, 31, 31, 31
};

uint_t TimeSharingScheduleClass::s_uLowDynamicPriorities[] = {
    0,  0,  0,  0,
    0,  0,  6,  6,
    6,  6,  6,  6,
    12, 12, 12, 12,
    12, 12, 12, 12,
    20, 20, 20, 20,
    20, 20, 26, 26,
    26, 26, 26, 26
};

int TimeSharingScheduleClass::s_nBaseTimeQuotas[] = {
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK
};

int TimeSharingScheduleClass::s_nMaxTimeQuotas[] = {
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    4 * TIMESHARING_QUOTAS_PER_TICK, 4 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK
};

uint_t TimeSharingScheduleClass::s_uReadyTickLimits[] = {
    200,   200,   200,   200,
    200,   200,   150,   150,
    150,   150,   150,   150,
    100,   100,   100,   100,
    100,   100,   100,   100,
    100,   100,   100,   100,
    100,   100,   65536, 65536,
    65536, 65536, 65536, 65536
};

uint_t TimeSharingScheduleClass::s_uPriorityIncrements[] = {
    16, 16, 16, 16,
    16, 16, 13, 13,
    13, 13, 13, 13,
    10, 10, 10, 10,
    10, 10, 10, 10,
    11, 11, 11, 11,
    11, 11, 0,  0,
    0,  0,  0,  0
};

uint_t TimeSharingScheduleClass::s_uTimeQuotaIncrements[] = {
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    1 * TIMESHARING_QUOTAS_PER_TICK, 1 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    2 * TIMESHARING_QUOTAS_PER_TICK, 2 * TIMESHARING_QUOTAS_PER_TICK,
    0 * TIMESHARING_QUOTAS_PER_TICK, 0 * TIMESHARING_QUOTAS_PER_TICK,
    0 * TIMESHARING_QUOTAS_PER_TICK, 0 * TIMESHARING_QUOTAS_PER_TICK,
    0 * TIMESHARING_QUOTAS_PER_TICK, 0 * TIMESHARING_QUOTAS_PER_TICK
};

TimeSharingScheduleClass g_timeSharingScheduleClass;
